package jjn.round1;

/**
 * @author Jjn
 * @since 2022-08-15 15:30
 */
public class SortingAlgorithm_InsertionSort implements SortAlgorithm {
    
    @Override
    public void sort(int... nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < nums.length; i++) {
            
            // 记录要插入的数据
            int tmp = nums[i];
            
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < nums[j - 1]) {
                nums[j] = nums[j - 1];
                j--;
            }
            
            // 存在比其小的数，插入
            if (j != i) {
                nums[j] = tmp;
            }
            
        }
    }
    
    private void swap(int i, int j, int... nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    @Override
    public String getName() {
        return "Insertion sort";
    }
}
